package test230530;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/30 20:18
 * 931. 下降路径最小和
 * https://leetcode.cn/problems/minimum-falling-path-sum/
 */
public class Solution04 {

    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        // dp[i][j] 表示 i j 位置时的最小下降路径和
        int[][] dp = new int[m+2][n+2];  // 多开空间, 简化边界判断
        // 状态初始化 第一行初始化0 防止 dp[1][i] 错误
        // 第一列和最后一列正无穷大, 防止迭代过程中被选中
        for (int i = 1; i <= m; ++i) {
            dp[i][0] = dp[i][n+1] = Integer.MAX_VALUE;
        }
        // 动态规划过程
        int res = Integer.MAX_VALUE; // 记录结果
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                // 当前位置的状态由 [i-1][j-1] [i-1][j] [i-1][j+1] 三个位置的状态决定
                int minVal = Math.min(Math.min(dp[i-1][j-1], dp[i-1][j]), dp[i-1][j+1]);
                dp[i][j] = minVal + matrix[i-1][j-1];
            }
        }
        // 计算结果
        for (int i = 1; i <= n; ++i) {
            res = Math.min(res, dp[m][i]);
        }
        return res;
    }
}
